package arithmetic.leetCode.yi;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-09-10
 * Time: 14:17
 */
public class ReverseKGroup {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(3);
        listNode.next.next.next = new ListNode(4);
        listNode.next.next.next.next = new ListNode(5);
        listNode.next.next.next.next.next = new ListNode(6);
        listNode.next.next.next.next.next.next = new ListNode(7);
        listNode.next.next.next.next.next.next.next = new ListNode(8);
        ListNode result = solve(listNode, 3);
        while (result != null) {
            System.out.print(result.val + "\t");
            result = result.next;
        }
    }


    public static ListNode solve(ListNode head, int k) {
        ListNode result = reversetLinkList(head);
        result = reverseKGroup(result, k);
        return reversetLinkList(result);
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode tmp = head;
        for (int i = 1; i < k && tmp != null; i++) {
            tmp = tmp.next;

        }
        if (tmp == null) {
            return head;
        }
        ListNode t2 = tmp.next;
        tmp.next = null;

        ListNode rGroupResult = reverseKGroup(t2, k);
        ListNode rVerseLinkList = reversetLinkList(head);
        head.next = rGroupResult;
        return rVerseLinkList;
    }

    private static ListNode reversetLinkList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode result = reversetLinkList(head.next);
        head.next.next = head;
        head.next = null;
        return result;

    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
